/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
/* 
 * Copyright (c) 2009 City University of Hong Kong
 * 
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License m_version 2 as
 * published by the Free Software Foundation;
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 * 
 * Author: Wilson Thong (wilsonwk@ee.cityu.edu.hk) 
 */
#include "bmsn-topology.h"
#include "ns3/ipv4-address.h"
#include <iostream>
#include <iomanip>
#include <sstream>

namespace ns3 {
namespace eecityu {

using namespace ns3;

NS_LOG_COMPONENT_DEFINE ("BmsnTopology");
//NS_OBJECT_ENSURE_REGISTERED (BmsnTopology);

/**
 * \brief Check if a number of a power of 2
 *
 * \param n The number to be tested
 * \param r A place holder for the function to return the number rows
 * of the BMSN topology, which is equal to sqrt(n). If n is not any
 * number raised to the power of 2, this r value is meaningless
 * \return True is the tested number n is a power of 2; false otherwise.
 */
bool IsPowOfTwo (uint32_t n, uint32_t& r) {
  // starting from r = 0, try all r*r and see if n == r*r could occur
  r = 0;
  while (r*r < n) r++;
  return r*r == n;
}

/**
 * \brief Get an octet from an IPv4 address
 *
 * \param addr An IPv4 address
 * \param i An index in the range 0, 1, 2, 3
 * \return Return the (i+1)-th octet from the given IPv4 address, where
 * the 1-st octet refers to the right-most (less-significant) octet of 
 * the IPv4 address
 */
uint32_t GetIpv4AddressAtOctet (const Ipv4Address& addr, uint32_t i)
{
  NS_LOG_FUNCTION (addr << i);

  // Get the ip address in 32-bit number representation
  uint32_t addrInNum = addr.Get ();
  // Count the number of octets the addrInNum should be shifted
  // to its right
  uint32_t count = i;

  while (count > 0) 
  {
    // shift the ip address number to the right by i*8-bit position
    // in order to shift the target octet to the left-most position
    addrInNum = (addrInNum >> 8);
    count--;
  }
  // return only the target octet 
  addrInNum = (addrInNum & 0xff);
  //NS_LOG_LOGIC ("The " << i 
  //  << "-th octet of the IP address " << addr 
  //  << " is " << addrInNum);
  return addrInNum;
}

/**
 * \brief Get the IPv4 address associated to a net device
 *
 * \param dev The net device from which an ip address is extracted
 * \return The IPv4 address associated with the given net device 
 */
Ipv4Address GetIpv4AddressFromNetDevice (const Ptr<const NetDevice> dev)
{
  NS_LOG_FUNCTION (dev);

  // get the IP address of the net device
  //
  // get the node of the net-device
  Ptr<Node> node = dev->GetNode ();
  NS_ASSERT_MSG (node, "No node is found to associate with the given net device.");
  // get the Ipv4 protocol from the node
  Ptr<Ipv4> ipv4 = node->GetObject<Ipv4> ();
  NS_ASSERT_MSG (ipv4, "No Ipv4 is found from the node housing the net device.");
  // get the interface index of the net-device of the node
  uint32_t inf = ipv4->GetInterfaceForDevice (dev);
  // return the IPv4 address obtained
  return ipv4->GetAddress (inf, 0).GetLocal (); 
}

/**
 * \param fromDev The net device from which a link begins
 * \param toDev The net device to which a link ends
 * \param nRows The number of rows in the BMSN topology
 *
 * \brief Check if the link is valid in a BMSN topology
 */
bool IsBmsnLink (Ptr<NetDevice> fromDev, Ptr<NetDevice> toDev, uint32_t nRows)
{
  NS_LOG_FUNCTION (fromDev << toDev << nRows);

  //// the number of nodes of the given BMSN topology
  //uint32_t nNodes = nRows * nRows;
  // get the IPv4 address from both the from-net-device and
  // the to-net-device
  Ipv4Address fromAddr = GetIpv4AddressFromNetDevice (fromDev);
  Ipv4Address toAddr   = GetIpv4AddressFromNetDevice (toDev  );
  NS_LOG_LOGIC ("IPv4 address of fromDev = " << fromAddr);
  NS_LOG_LOGIC ("IPv4 address of toDev   = " << toAddr);
  // extract the last three octets of the IPv4 address of the
  // from-net-device. The three octet are x, y, and z and are
  // corrsponding to the IPv4 address "w.x.y.z"
  uint32_t fromAddrOctetZ = GetIpv4AddressAtOctet (fromAddr, 0);
  uint32_t fromAddrOctetY = GetIpv4AddressAtOctet (fromAddr, 1);
  uint32_t fromAddrOctetX = GetIpv4AddressAtOctet (fromAddr, 2);
  // extract the last three octets of the IPv4 address of the
  // to-net-device. The three octet are x, y, and z and are
  // corrsponding to the IPv4 address "w.x.y.z"
  uint32_t toAddrOctetZ = GetIpv4AddressAtOctet (toAddr, 0);
  uint32_t toAddrOctetY = GetIpv4AddressAtOctet (toAddr, 1);
  uint32_t toAddrOctetX = GetIpv4AddressAtOctet (toAddr, 2);
  // set to true if the link bewteen the two net devices is a valid BMSN link
  bool isBmsnLink = false;
  switch (fromAddrOctetZ) 
  {
  // North facing link
  case 1:
    isBmsnLink = 
      (
      toAddrOctetZ == 3 && 
      toAddrOctetY == (fromAddrOctetY+nRows-1) % nRows &&
      toAddrOctetX == fromAddrOctetX
      );
    break;

  // East facing link
  case 2:
    isBmsnLink = 
      (
      toAddrOctetZ == 4 && 
      toAddrOctetY == fromAddrOctetY &&
      toAddrOctetX == (fromAddrOctetX+1) % nRows
      );
    break;

  // South facing link
  case 3:
    isBmsnLink = 
      (
      toAddrOctetZ == 1 && 
      toAddrOctetY == (fromAddrOctetY+1) % nRows &&
      toAddrOctetX == fromAddrOctetX
      );
    break;

  // West facing link
  case 4:
    isBmsnLink = 
      (
      toAddrOctetZ == 2 && 
      toAddrOctetY == fromAddrOctetY &&
      toAddrOctetX == (fromAddrOctetX+nRows-1) % nRows
      );
    break;

  // Error case!
  default:
    NS_ASSERT_MSG (false, "Invalid IPv4 address (fromAddr = " << fromAddr 
      << ") for a BMSN link. The last octet of the IP address \
         must be 1, 2, 3 or 4.");
  }

  return isBmsnLink;
}

///** 
// * \todo Include m_version number and m_version checking functions
// */
//TypeId 
//BmsnTopology::GetTypeId (void)
//{
//  static TypeId tid = TypeId ("ns3::eecityu::BmsnTopology")
//    .SetParent<Object> ()
//    .AddConstructor<BmsnTopology> ()
//    ;
//
//  return tid;
//}

BmsnTopology::BmsnTopology(void)
{
  NS_LOG_FUNCTION_NOARGS ();

}

void BmsnTopology::SetNodesAndNetDevices (
  const NodeContainer& nodes, 
  const NetDeviceContainer& devs)
{
  //NS_LOG_FUNCTION (nodes << devs);

  // do not allow calling this method more than once
  NS_ASSERT_MSG (IsEmpty (), "BMSN topology exists already and cannot be set again.");
  // add the nodes and net devices into this object
  m_nodes.Add (nodes);
  m_devices.Add (devs);
  // do not allow setting a non BMSN topology
  NS_ASSERT_MSG (IsBmsnTopology (), "This is not a BMSN topology!");
}

bool BmsnTopology::IsEmpty () const
{
  return
    GetNNodes () == 0 &&
    GetNLinks () == 0;
}

/**
 * \todo Jun 9, 2009 check the first octet of the ip address of net devices
 * and only allow the octet to be in the range [1, 127]; i.e., 
 * the IP address must be a Class-A address
 */
bool BmsnTopology::IsBmsnTopology () const
{
  NS_LOG_FUNCTION_NOARGS ();

  // True if the number of nodes is correct
  uint32_t nNodes = GetNNodes ();
  // To contain the number of rows of the BMSN topology.
  uint32_t nRows = 0;
  // check and see if nNodes is some number raised to the power of 2,
  // and, if so, return its square root of the nNodes and write to
  // the nRows variable
  bool isNNodes = IsPowOfTwo (nNodes, nRows);
  NS_ASSERT_MSG (nNodes, "No node is found. BMSN topology cannot be empty.");
  NS_LOG_LOGIC ("Correct number of nodes: " << isNNodes);
  NS_LOG_LOGIC ("Number of nodes  = " << nNodes);
  NS_LOG_LOGIC ("Number of rows   = " << nRows);
  // True if the number of links is correct
  uint32_t nLinks = GetNLinks ();
  bool isNLinks = ( GetNNodes () * 2 == nLinks );
  NS_ASSERT_MSG (nLinks, "No link is found. BMSN nodes cannot be all isolated.");
  NS_LOG_LOGIC ("Correct number of links: " << isNLinks);
  NS_LOG_LOGIC ("Number of links = " << nLinks);
  // True if the link between two net devices is a valid BMSN link.
  // It is set to true initially to allow a recursive AND operation
  // to start.
  bool isAllBmsnLinks = true;
  // an index indicating which net device the following loop
  // is now considering
  uint32_t walkToNetDevice = 0;
  // Walk all net devices and check if they connect to the correct
  // neighboring net device
  for (NetDeviceContainer::Iterator devIter = m_devices.Begin ();
  // The isAllBmsnLinks makes sure that this loop is broken whenever
  // there is one single link found to be not valid for BMSN topology
    devIter != m_devices.End () && isAllBmsnLinks; 
    devIter++)
  {
    NS_LOG_LOGIC ("Checking net device = " << walkToNetDevice);
    // The net device on one end of a point-to-point channel
    Ptr<NetDevice> dev1 = *devIter;
    // Confirm there are exactly two net devices connected 
    // to the point-to-point channel
    uint32_t nDevices = dev1->GetChannel ()->GetNDevices ();
    NS_ASSERT_MSG (nDevices == 2, "A link in a BMSN topology \
                                  must connect to exactly 2 net devices.");
    // Get the net device on the other end of the point-to-point channel.
    Ptr<NetDevice> dev2 = dev1->GetChannel ()->GetDevice (0);
    // The GetDevice (0) may return the "dev1" itself. If so,
    // the other net devices must be "dev2" and GetDevice (1) 
    // will be correct
    if (dev1 == dev2) dev2 = dev1->GetChannel ()->GetDevice (1);
    // IsBmsnLink has to be true always or the topology is not BMSN
    bool isBmsnLink = IsBmsnLink (dev1, dev2, nRows);
    NS_LOG_LOGIC ("Correct BMSN link = " << isBmsnLink);
    isAllBmsnLinks = isAllBmsnLinks && isBmsnLink;
    // update this index to indicate correctly which net device
    // this for loop is now considering
    walkToNetDevice++;
  }
    
  return isNNodes && isNLinks && isAllBmsnLinks;
}

string 
BmsnTopology::GetNodePosition (Ptr<Node> n) const
{
  NS_LOG_FUNCTION (n);

  // Get the IPv4 address of one of the node's interface
  // and read the x- and y-coordinate 
  Ptr<Ipv4> ipv4 = n->GetObject<Ipv4> ();
  Ipv4Address addr = ipv4->GetAddress (1, 0).GetLocal ();
  // The x-coordinate of from the IPv4 address
  uint32_t xPos = GetIpv4AddressAtOctet (addr, 2);
  // The y-coordinate of from the IPv4 address
  uint32_t yPos = GetIpv4AddressAtOctet (addr, 1);
  // prepare a string to description of the node's position
  ostringstream os;
  os << setiosflags (ios::left | ios::showpoint) << setprecision (4);
  os << " " << setw(10) << (xPos + 1) / (double) (GetNRows () + 1)
     << " " << setw(10) << (yPos + 1) / (double) (GetNRows () + 1)
     << " " << setw(10) << 0.5;
  // return the position string
  return os.str ();
}

uint32_t 
BmsnTopology::GetNRows () const
{
  uint32_t root;
  NS_ASSERT_MSG (IsPowOfTwo (GetNNodes (), root), "The number of nodes in this BMSN topology is not a power of two of some integer.");

  return root;
}

} // namespace eecityu
} // namespace ns3

